package DFS递归搜索与回溯.递归;

import java.util.List;

/**
 * @Date 2024/9/11 21:18
 * @description: 汉诺塔: 经典递归问题
 * .        https://leetcode.cn/problems/hanota-lcci/description/
 * @Author LittleNight
 */
public class likou0806 {


    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        // 相信dfs 能完成: 借助于 B 这个柱子, A 能把a上的所有盘子转移到C 上
        dfs(A, B, C, A.size());
    }

    private void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {
        // 递归出口, 就一个盘子, 直接就是移动到C上
        if(n == 1) {
            // 为什么不是get, 因为a上面的要移走, 而不是不动
            // c.add(a.get(a.size() - 1));
            c.add(a.get(a.size() - 1));
            return;
        }
        // 主逻辑.
        // 1. 先把 a 上的n-1个转移到b上
        dfs(a, c, b, n - 1);
        // 2. 再把 a 上的一个盘子添加到c上
        c.add(a.get(a.size() - 1));
        // 3. 在把b上的n-1个盘子转移到c上
        dfs(b, a, c, n - 1);
    }

}
